快慢指针

实际上，双指针是一个很笼统的概念。只要在解题时用到了两个指针（链表指针、数组下标皆可），都可以叫做双指针方法。根据两个指针运动方式的不同，双指针方法可以分成同向指针、对向指针、快慢指针等。

当双指针方法遇到链表问题，我们主要使用快慢指针方法。很多时候链表操作遇到疑难杂症时，可以使用快慢指针，减少算法所需的时间或者空间。

我们知道，链表数据类型的特点决定了它只能单向顺序访问，而不能逆向遍历或随机访问（按下标访问）。很多时候，我们需要使用快慢指针的技巧来实现一定程序的逆向遍历，或者减少遍历的次数。这就是为什么快慢指针常用于链表问题。

LeetCode 876 - Middle of the Linked List[4]（Easy）

寻找链表中点的常规做法是，先遍历一遍链表，计算链表的长度 。再遍历一遍链表，找到第  n 个元素。这样需要遍历链表两遍。更巧妙的做法是使用一快一慢两个指针。

public ListNode middleNode(ListNode head) {

    ListNode fast = head;

    ListNode slow = head;

    while (fast != null && fast.next != null) {

        // fast 一次前进两个元素，slow 一次前进一个元素

        fast = fast.next.next;

        slow = slow.next;

    }

    // 链表元素为奇数个时，slow 指向链表的中点

    // 链表元素为偶数个时，slow 指向链表两个中点的右边一个

    return slow;

}

LeetCode 19 - Remove Nth Node From End of List[5]（Medium）

寻找链表的倒数第  个元素的常规做法是，先遍历一遍链表，计算链表的长度 。这样就可以计算出要找第  n个元素，再遍历一遍链表即可。这里同样可以使用快慢指针方法减少一次遍历。

public ListNode removeNthFromEnd(ListNode head, int k) {

    // 将 fast 前进 k 个元素

    ListNode fast = head;

    for (int i = 0; i < k; i++) {

        // 这里省略了检测空指针的代码

        fast = fast.next;

    }

    // fast 和 slow 指针间隔 k 个同时前进

    // 这里使用了链表遍历框架，将 slow 指针变成两个指针 curr 和 prev

    ListNode curr = head;

    ListNode prev = null;

    while (fast != null) {

        prev = curr;

        curr = curr.next;

        fast = fast.next;

    }

    if (prev == null) {

        head = curr.next;

    } else {

        prev.next = curr.next;

    }

    return head;

}

LeetCode 141 - Linked List Cycle[6]（Easy）

public boolean hasCycle(ListNode head) {

    ListNode fast = head;

    ListNode slow = head;

    while (fast != null && fast.next != null) {

        fast = fast.next.next;

        slow = slow.next;

        // fast 和 slow 指向同一个结点，说明存在“套圈”

        if (fast == slow) {

            return true;

        }

    }

    // fast 到达链表尾部，则不存在环

    return false;

}

这一题还有第二问，LeetCode 142 - Linked List Cycle II[7]，找到链表入环的第一个结点。

本文讲解的是双指针技巧中的一类“快慢指针”，用于解决链表类问题。而快慢指针又存在着多个变种，文中也一一列举了。

链表类题目并不复杂，本系列第一讲的链表遍历框架和本文所讲的快慢指针就是链表类问题中最主要的两个技巧了。链表类问题只要多加练习，都非常的容易。

最后，附上一道链表问题的综合练习题：链表排序（LeetCode 148 - Sort List[8]）。这道题中需要使用到链表处理的各种技巧，还需要针对链表的性质选择合适的排序方法。可以说只要掌握了这道题，就算掌握了链表类问题了。链表排序也是微软面试中某个面试官的“三板斧”之一，可以看出这道题的普适性。

上一讲和这一讲我们分别了解了两种不同类型的双指针方法：对向指针和快慢指针。双指针还有一种经典的类型是滑动窗口，将在后面的章节进行讲解。敬请期待。

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序的性能不受输入数据的影响，始终都是 O(nlogn) 的时间复杂度，代价是需要额外的内存空间。

算法原理

① 把长度为n的输入序列分成两个长度为n/2的子序列；

② 对这两个子序列分别采用归并排序；

③ 将两个排序好的子序列合并成一个最终的排序序列。

将两个的有序数列合并成一个有序数列，我们称之为"归并"。

归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

1、从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。(参考下面的图片)

2、从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：

① 分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2;

② 求解：递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。

③ 合并：将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

下面的图片很清晰的反映了"从下往上"和"从上往下"的归并排序的区别。

归并排序(从上往下)参考小波同学“归并排序(从上往下)——内存优化——推荐方式”代码；归并排序(从下往上)参考小波同学MergeSort2代码。

LeetCode 148 - Sort List[1]（Medium）: 用 O(nlogn) 级别的时间复杂度、常数级空间复杂度，对链表进行排序。

这个系列到目前为止已经讲了两期链表类问题了，分别是链表遍历框架、链表快慢指针。链表类问题并不复杂，这两大方法已经可以基本涵盖大部分的链表题目了。

本期所讲的链表排序问题是一道经典的链表综合题。在面试中，这道题非常常见，甚至是微软某面试官常用的”三板斧“之一，足以看出它的普适性。这道题需要用到链表问题各种常见的方法和操作。同时，它又涉及到将传统的数组排序方法迁移到链表，可以考察面试者对排序算法的理解。具体来说，链表排序这道题可以考察：对链表性质的掌握、对分治法的掌握、对链表操作的掌握

选择排序方法

首先，我们要理解链表问题的基本原则，不使用额外的空间。也就是说，不使用 new 关键字。

明确了这个原则之后，我们再来看这道题目。题目要求使用  nlogn级别的排序算法。回顾我们学过的排序算法，很显然，我们需要在快速排序、归并排序、堆排序中进行选择。

链表相对于数组最大的不同，在于链表只能进行顺序访问，甚至只能进行正向顺序访问，不能进行随机访问（按下标访问）。而考虑到快速排序、堆排序都涉及到大量的随机访问，必然排除。剩下的归并排序，仔细思考之后，确实可以只用顺序访问。那么，我们可以将归并排序方法应用到链表排序上。

链表切分

链表的切分需要将链表平分为左右两半。这个操作实际上可以拆分为两个基本操作：寻找链表的中点、删除链表中点左侧的指针，将链表断开。寻找链表中点的操作，我们在链表快慢指针的文章中讲过，使用一快一慢两个指针遍历链表即可。删除链表指针，实际上和删除链表结点类似。我们在链表遍历框架的文章中讲过，使用相邻的两个指针一同遍历链表即可。

那么如何将这两个方法融合起来呢？我们使用三个指针即可，分别是快指针、慢指针、慢指针的前一个指针。这样当快指针到达链表尾部时，慢指针的前一个结点正好是我们要删除的指针。

三个指针的移动过程

ListNode split(ListNode head) {

    ListNode fast = head;

    ListNode slow = head;

    ListNode prev = null;

    while (fast != null && fast.next != null) {

        fast = fast.next.next;

        prev = slow;

        slow = slow.next;

    }

    prev.next = null;// 将链表断开

    return slow;

}

链表合并

如何将两个有序的链表合并成一整个有序链表呢？其实，链表的合并也是一种基本操作，例如这一题，考的就是链表合并：

LeetCode 21 - Merge Two Sorted Lists[3]（Easy）

// 全局变量，用于将结点插入链表尾部

ListNode head;

ListNode tail;

ListNode merge(ListNode left, ListNode right) {

    head = null;

    tail = null;

    ListNode q1 = left;

    ListNode q2 = right;

    while (q1 != null || q2 != null) {

        if (q1 == null) {

            append(q2);

            q2 = q2.next;

        } else if (q2 == null) {

            append(q1);

            q1 = q1.next;

        } else if (q1.val < q2.val) {

            append(q1);

            q1 = q1.next;

        } else {

            append(q2);

            q2 = q2.next;

        }

    }

    return head;

}

void append(ListNode node) {

    if (head == null) {

        head = node;

        tail = node;

    } else {

        tail.next = node;

        tail = node;

    }

}

全部代码

到了这里，链表排序的全部代码已经完成了。下面是完成的题解代码：

public ListNode sortList(ListNode head) {

    if (head == null || head.next == null) {

        return head;

    }

    ListNode mid = split(head);

    ListNode left = sortList(head);

    ListNode right = sortList(mid);

    return merge(left, right);

}

ListNode split(ListNode head) {

    ListNode fast = head;

    ListNode slow = head;

    ListNode prev = null;

    while (fast != null && fast.next != null) {

        fast = fast.next.next;

        prev = slow;

        slow = slow.next;

    }

    prev.next = null;

    return slow;

}

ListNode head;

ListNode tail;

ListNode merge(ListNode left, ListNode right) {

    head = null;

    tail = null;

    ListNode q1 = left;

    ListNode q2 = right;

    while (q1 != null || q2 != null) {

        if (q1 == null) {

            append(q2);

            q2 = q2.next;

        } else if (q2 == null) {

            append(q1);

            q1 = q1.next;

        } else if (q1.val < q2.val) {

            append(q1);

            q1 = q1.next;

        } else {

            append(q2);

            q2 = q2.next;

        }

    }

    return head;

}

void append(ListNode node) {

    if (head == null) {

        head = node;

        tail = node;

    } else {

        tail.next = node;

        tail = node;

    }

}

总结

链表排序问题并不难，但是作为综合题，考察的是方方面面的知识。我们需要理解链表遍历框架、链表快慢指针这些基本操作，还需要清除链表的性质，选择合适的排序算法，并从已有的数组排序方法中迁移知识。如果你要准备面试的话，不妨把这道题做熟练了，对于链表类问题是一个很好的总结。

相关文章：

LeetCode 例题精讲 | 01 反转链表：如何轻松重构链表

LeetCode 例题精讲 | 05 双指针×链表问题：快慢指针